NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses external files.)

Title: Graph Coloring using Asynchronous Weak-Commitment with the resolved-based learning (new interface)
Author: Ionel Muscalagiu and Jose M. Vidal
Description:
This is the implementation of the Asynchronous Weak-Commitment Search with the resolved-based learning for the graph coloring problem. We solve the graph coloring problem using the AWCS algorithm from
<ul>
<li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/library/yokoo00a.pdf">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000. <a href="http://dx.doi.org/10.1023/A:1010078712316">doi:10.1023/A:1010078712316</a>
</li>
</ul>
and the resolvent-based learning from
<ul>
<li>Katsutoshi Hirayama and Makoto Yokoo. <a href="http://lang.is.kyushu-u.ac.jp/~yokoo/PDF/icdcs-2000-nglearn.pdf"> The Effect of Nogood Learning in Distributed Constraint Satisfaction</a>. <i>In Proceedings of the 20th IEEE International Conf. on Distributed Computing Systems,</i> pages 169--177, 2000.
</li>
</ul>
In this paper it presents a resolvent-based nogood learning method as a new nogood learning method for distributed CSP algorithms, which is based on a look-back technique in CSP. This method can be summarized as follows: for each possible value for a deadend variable, select one nogood that prohibits the value, then make a new nogood out of the aggregation of these selected nogoods. The nogood made in this way is virtually equivalent to a resolvent in the propositional logic, so we refer to this method as resolvent-based learning.
Nogood learning methods can drastically reduce cycles consumed to find a solution and produce an effective nogood with fewer nogood checks. With the help of the resolvent-based nogood learning method, agents can decide values to variable more adequately and thus reduces the communication cost in AWCS.